Forum:Sigma project
We should create a central hub page (in the project namespace probably) for the ongoing project of evaluating Sigma(5). (As a sidenote, I think we should devise a more concise TM notation that doesn't take up, like, 20 lines.) Where is the most up-to-date content on this subject? it's vel 02:48, September 28, 2014 (UTC) :I think I'd be a good idea to make sections here about proofs. There is no up-to-date content, all proofs are invalid. Wythagoras (talk) 08:27, September 28, 2014 (UTC) Simulations HNR #3 Simulated up to 81.8 billion steps. Let me know today if you need to know anything about simulation. Also, there is no reason why the machine's name is 5-state BB (4098), I dunno how it came there. Wythagoras (talk) 10:44, September 28, 2014 (UTC) Confession (and proofs for 14 HNRs) On around November of last year, I picked Sigma(5) as the subject of an R&E project for my school. I have proven 14 of the 42 HNRs to loop using Heiner Marxen's AWK script, and on this year I used the result for my graduation paper. The professor suggested to post the results here, which I hesitated to do until now. The proven HNRs are #02, #05, #06, #08, #11, #14, #18, #20, #21, #22, #25, #27, #30 and #38. Download the results here. Let me know if you need to know more about this. (I might release it as a blog post.) -- ☁ I want more ⛅ 11:17, September 28, 2014 (UTC) :Wow, great job! Wythagoras (talk) 11:26, September 28, 2014 (UTC) :This is really awesome! Finally a result about which we can be sure. Just curious, how much time did the evaluation take for all these machines? LittlePeng9 (talk) 11:28, September 28, 2014 (UTC) :Daniel Briggs also proved some machines are non-halting or gave clues to prove some. Machines #02-#13, #15, #17, #18, #21, #23, #25-36, #38 and #39 are proven or given some clues. Also, #01 was almost completely proven (see below). Daniel Briggs and univerz prove some machines are non-halt. So, we left with #16, #19, #24, #37 and #40-42 (43?). Under ten machines are holdouts now. Tetramur (talk) 09:56, May 5, 2019 (UTC) Observation for HNR#1 I've tried to simulate it for different inputs - it exhibits quite weird behavior for a while, then it either halts or falls to simple loop with states 4-1-3-4-2-3-4-2-3-0-4 and quickly appending ones to the right. The latter situation happens if we have ..._111 at the tape, where head is place at the last 1 and state is 3 or 4. Also, from my experiments, it halts only when head is placed to the left of all sequences of 1's. Ikosarakt1 (talk ^ ) 04:35, February 2, 2015 (UTC) : This machine also halts if ran on input __1 with initial state 0. Note that at one point machine is in state 0 between some 1's, so observation from your experiments seems to be incorrect. LittlePeng9 (talk) 11:27, February 2, 2015 (UTC)